Many databases have already or will soon have grown to the point where the production of useful views of the entire database at real-time (interactive) rates is impossible. In many cases (for example, high resolution spatial databases), it would be acceptable to work with a reduced-resolution representation that approximates the original database and that is small enough to be manipulated and viewed in real time. The representation should do the best job of approximating the original database at some given size for the representation. In other words, the representation should be optimal. Furthermore, the representation, in general, will need to be tailored to the particular views that are to be generated. This implies that the representation itself must be produced in real time. Finally, since the size of databases will only continue to grow, the methods for producing reduced-resolution representations should not impose any inherent limits on the size of the databases that can be approximated.
The invention described here, dubbed ROAM for Real-time Optimally Adapting Meshes, is a general method for producing optimal-quality, reduced-resolution approximate representations of arbitrarily large databases in real time. For example, in an exemplary embodiment discussed below for terrain rendering, the ROAM method is used to produce a reduced-resolution representation of a large terrain database that is optimized for viewing from a given location with a given direction and field of view. The representation can be produced at a rate of 30 frames per second (or faster) making the process appropriate for interactive fly-over of the terrain. In comparison with other methods of approximating a terrain for interactive viewing, ROAM produces approximate representations of much higher quality resulting in a dramatic reduction in visual artifacts as compared with other methods of approximating a terrain for interactive viewing.
In addition to requiring a reduced-resolution representation to be optimal, there will often be cases in which certain features need to be represented exactly, that is, as they would be if no reduction in resolution had taken place. ROAM includes a very general mechanism for guaranteeing that distinguished features of the database are exact in the representations that it produces. In many cases, this can be done with negligible effect on the quality of other features (which are still being approximated) or the speed with which the representation is produced. For example, in the exemplary embodiment for terrain rendering, ROAM can guarantee that lines of sight from the eye to distinguished targets are exact (that is, clear or occluded as they would be if the exact terrain were used) in the terrain representation that it produces for interactive viewing. ROAM can make this guarantee for dozens to hundreds of distinguished lines of sight with negligible effect on either performance or the overall quality of the approximated terrain. The ability to guarantee exact lines of sight in scenes generated in real time is obviously important in, for example, simulations for training of military pilots.
ROAM's ability to produce approximate representation in which essentially arbitrary features are exactly represented is a major advance in solving the difficult problem of maintaining consistency between real-time simulations, which must be able to interact while remaining free to choose their own approximations for terrain and other databases in order to fit their individual computational capabilities, and needs for accuracy. In such situations, ROAM maintains consistency by allowing each simulation system to construct its own representation subject to the condition that the features that must be consistent are represented exactly.
Terrain remains one of the most challenging types of large spatial databases for visualization because it is not naturally decomposed into parts whose complexity can be adjusted independently, and because the qualities required of a triangulation are view dependent. Classic geometry level-of-detail (LOD) optimization algorithms are not immediately applicable to terrain because they require independently adjustable parts. Traditional triangulation optimizations do not apply directly to terrain visualization because they do not admit flexible view-dependent error objectives, and they are much too slow to be used for each frame.
Known existing algorithms that can interactively perform view-dependent, locally-adaptive terrain meshing, including the process of the present invention, rely on a pre-defined multiresolution terrain representation that is used to build the adaptive triangle mesh for a frame. Typically, neighborhoods that are flat or distant are triangulated more coarsely than close or rough neighborhoods that require finer details. See, e.g., Mark C. Miller, "Multiscale Compression of Digital Terrain Data to Meet Real time Rendering rate Constraints," University of California-Davis, graduate thesis (1995), incorporated herein by reference.
On current graphics hardware and software, the problem remains to maintain dynamic, view-dependent triangle meshes and texture maps that produce good images at the required frame rate. Using ROAM, meshes are constructed that optimize flexible view-dependent error metrics, produce guaranteed error bounds, achieve specified triangle counts directly, and use frame-to-frame coherence to operate at high frame rates for thousands of triangles per frame.
Various objects, advantages and novel features of ROAM will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.